#leetcode题目16：最接近的三数字和   
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：双指针
#目前暂时还没有吃透
from typing import List
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res=nums[0]+nums[1]+nums[len(nums)-1]
        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1
            while left<right:
                val=nums[i]+nums[left]+nums[right]
                if abs(val-target)<abs(res-target):
                    res=val
                if val==target:
                    return target
                if val<target:
                    left+=1
                else:
                    right-=1
        return res
      
        
#测试数据
nums=[-1,2,1,-4]
target=1
#预期输出：2，因为-1+2+1=2，最接近1
solution=Solution()
print(solution.threeSumClosest(nums,target))